package com.sunqianhu.algorithm.sort.select.heap_sort;

public class HeapSort {


    //建立大顶堆
    //arr：元素集合，n：元素个数，i：堆顶索引
    public void heapify(int[] arr, int n, int i){
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        //得堆顶值的元素索引
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        //如果最大值的索引不等于当前对顶索引，则交换对顶与最大值
        if (largest != i) {
            int swap = arr[i]; //当前对顶元素
            arr[i] = arr[largest]; //当前最大值放到对顶
            arr[largest] = swap; //当前值放到子节点中
            //此时largest为原子节点索引，由于值变了，需要重新递归计算该子节点下的节点需不需要调整位置。
            heapify(arr, n, largest);
        }
    }

    // 堆排序方法
    public void sort(int[] arr) {
        int n = arr.length;
        //建立大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        //一个个从堆中取出元素
        for (int i = n - 1; i >= 0; i--) {
            int temp = arr[0]; //选择第一个最大的堆顶元素
            arr[0] = arr[i]; //大顶堆的最后一个元素放到堆顶
            arr[i] = temp; //选择的最大堆顶元素放到堆的最后
            //排查最后一个元素，从新建立大顶堆
            heapify(arr, i, 0);
        }
    }

    // 打印数组的方法
    static void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        int n = arr.length;

        HeapSort hs = new HeapSort();
        System.out.println("原始数组:");
        printArray(arr);

        hs.sort(arr);

        System.out.println("排序后数组:");
        printArray(arr);
    }
}
